public class Dynamic {
    public static void main(String[] args) {
        int[] w={1,4,3};//物品重量
        int[] val={1500,3000,2000};//物品价格
        int n=val.length;//物品个数
        int m=4;//包的容量

        int[][] v=new int[n+1][m+1];
        int[][] path=new int[n+1][m+1];//用来标记有最优解的位置

        for (int i = 0; i < v.length; i++) {//将第一列置零
            v[i][0]=0;
        }
        for (int i = 0; i < v.length; i++) {//将第一行置零
            v[0][i]=0;
        }

        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[0].length; j++) {
                if (w[i-1]>j){//如果i-1物品的重量大于最大重量j就将i-1这个较小重量物品装进去
                    v[i][j]=v[i-1][j];
                }else {
                    if (v[i-1][j]<val[i-1]+v[i-1][j-w[i-1]]){//如果i物品的重量小于j，则将i-1这个重量本身的值+i-1中出去i的价值中所能找到的物品的最大值
                    v[i][j]=val[i-1]+v[i-1][j-w[i-1]];
                    path[i][j]=1;
                }else {
                        v[i][j]=v[i-1][j];
                    }
            }
        }
    }

        for (int i = 0; i < v.length; i++) {//遍历输出
            for (int j = 0; j < v[0].length; j++) {
                System.out.print(v[i][j]+" ");
            }
            System.out.println();
        }

        int i= path.length-1;//最后一个值的下标
        int j=path[0].length-1;//最后一个值的下标
        while (i>0&&j>0){
           if (path[i][j]==1){//表示有最优解
               System.out.println("第"+i+"个物品放入包中");
               j-=w[i-1];//减去装入的物品的重量，得到剩余可以再装物品的重量
           }
           i--;//
       }


    }
}
